package lib;

public class Arithmetic {
	/** Method is tested and works well */
	public static int gcd(int factorA, int factorB) {
		if(factorB == 0) {
			return factorA;
		}
		
		int tmp = factorA % factorB;
		while(tmp != 0) {
			factorA = factorB;
			factorB = tmp;
			tmp = factorA % factorB;
		}
		
		return factorB;
	}
	/** Method is tested and works well - up to 300 000 in 1 second, largest prime ~ 4 000 000 */
	public static int[] getFirstPrimes(int nrPrimes) {
		int[] res = new int[nrPrimes];
		if(nrPrimes == 0) {
			return res;
		}
		
		res[0] = 2;
		int cInd = 1;
		for(int i = 3; cInd < nrPrimes; i += 2) {
			boolean isPrime = true;
			for(int j = 0; j < cInd && res[j] * res[j] <= i; j++) {
				if(i % res[j] == 0) {
					isPrime = false;
					break;
				}
			}
			if(isPrime) {
				res[cInd] = i;
				cInd++;
			}
		}
		
		return res;
	}
	/** Method is tested and works well - up to 10^15 in 1 second */
	public static boolean isPrime(long testNumber) {
		if(testNumber == 1) {
			return false;
		}
		
		if(testNumber > 2 && testNumber % 2 == 0) {
			return false;
		}
		
		int max = (int)Math.sqrt(testNumber) + 2;
		for(int i = 3; i < max; i += 2) {
			if(testNumber % i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	/** Based on recurrence rule: c(k + 1, n + 1) = c(k, n) + c(k + 1, n) 
	 *  Method is tested and works well. */
	public static long[][] binom = new long[51][51];
	public static long binomialCoeficient(int k, int n, long mod) {
		if(k == n) {
			return 1;
		}
		if(k == 0) {
			return 1;
		}
		if(n == 0) {
			return 0;
		}
		
		if(binom[k][n] != 0) {
			return binom[k][n];
		}
		
		binom[k][n] = (binomialCoeficient(k - 1, n - 1, mod) + binomialCoeficient(k, n - 1, mod)) % mod;
		return binom[k][n];
	}
	
	/** Method is tested and works well */
	public static long gcd(long factorA, long factorB) {
		if(factorB == 0) {
			return factorA;
		}
		
		long tmp = factorA % factorB;
		while(tmp != 0) {
			factorA = factorB;
			factorB = tmp;
			tmp = factorA % factorB;
		}
		
		return factorB;
	}
	
	public static void main(String[] args) {
		Arithmetic app = new Arithmetic();
		long a = System.currentTimeMillis();
		long coef = binomialCoeficient(25, 50, 1000000003);
		long b = System.currentTimeMillis();
		System.out.println(coef + " - " + (b - a));
	}
}
